Sort Integers by The Number of 1 Bits

LeetCode 1458 | Difficulty: Easy

Easy

Problem Description

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints:

- `1 <= arr.length <= 500`

- `0 <= arr[i] <= 10^4`

Topics: Array, Bit Manipulation, Sorting, Counting

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 240 ms)

Metric	Value
Runtime	240 ms
Memory	32.3 MB
Date	2020-02-26

Solution

public class Solution {
    public int[] SortByBits(int[] arr) {
       Array.Sort(arr, new BitCountComparer());
    return arr;
}

public class BitCountComparer : IComparer<int>
{
    public int Compare(int x, int y)
    {
        int x_bits = CountBits(x);
        int y_bits = CountBits(y);
        if (x_bits == y_bits)
        {
            return x.CompareTo(y);
        }
        else
        {
            return x_bits.CompareTo(y_bits);
        }
    }
    
    private int CountBits (int n)
    {
        int count = 0;
        while(n!=0)
        {
            count++;
            n = n&n-1;          
        }
        return count;
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Simulate the problem. Count the number of 1's in the binary representation of each integer.

Hint 2: Sort by the number of 1's ascending and by the value in case of tie.